package com.mark.algorithms.text;

/**
 * KMP 字符串检索
 * 
 * @author Mark Hsiu
 *
 */
public class KMPString {

	private final static String m_str = "abcabaabcaabac";
	private final static String c_str = "abaa";

	public static void main(String[] args) {
		common();
		common1();
		System.out.println("=====================");
		kmp();
	}

	/**
	 * 简单模式匹配算法的运行时间为O（(n-m+1)m）
	 */
	public static void common() {
		char[] mstrs = m_str.toCharArray();
		char[] cstrs = c_str.toCharArray();
		int mSize = mstrs.length;
		int cSize = cstrs.length;
		int mIndex = 0;
		boolean success = false;
		for (int i = 0; i < mSize - cSize + 1;) {
			for (int j = 0; j < cSize; j++, i++) {
				if (mstrs[i] != cstrs[j]) {
					mIndex++;
					i = mIndex;
					break;
				}

				if (j == cSize - 1) {
					success = true;
					break;
				}

			}

			if (success) {
				System.out.println((i - cSize + 1) + " -->>> " + i);
				break;
			}

		}
	}

	/**
	 * O(pattern_length*target_length)
	 */
	public static void common1() {
		char[] target = m_str.toCharArray();
		char[] pattern = c_str.toCharArray();
		int target_length = target.length;
		int pattern_length = pattern.length;
		int target_index = 0;
		int pattern_index = 0;
		while (target_index < target_length && pattern_index < pattern_length) {
			if (target[target_index] == pattern[pattern_index]) {
				++target_index;
				++pattern_index;
			} else {
				target_index -= (pattern_index - 1);
				pattern_index = 0;
			}
		}
		if (pattern_index == pattern_length) {
			System.out.println(target_index - pattern_length);

		} else {
			System.out.println(-1);

		}
	}

	/**
	 * KMP 模式匹配
	 */
	public static void kmp() {
		char[] target = m_str.toCharArray();
		char[] pattern = c_str.toCharArray();
		int target_length = target.length;
		int pattern_length = pattern.length;
		int[] overlay = compute_overlay(pattern, pattern_length);

		for (int i : overlay) {
			System.out.print(i + " ");
		}
	}

	/**
	 * a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
则对于pattern的前j+1序列字符，则有如下可能
⑴     pattern[k+1]==pattern[j+1] 此时overlay(j+1)=k+1=overlay(j)+1
⑵     pattern[k+1]≠pattern[j+1] 此时只能在pattern前k+1个子符组所的子串中找到相应的overlay函数，
h=overlay(k),如果此时pattern[h+1]==pattern[j+1],则overlay(j+1)=h+1否则重复(2)过程.

	 * 覆盖函数 a ab aba abaa
	 * 
	 * @return
	 */
	private static int[] compute_overlay(char[] pattern, int pattern_length) {
		int[] overlay = new int[pattern_length];
		overlay[0] = -1;
		
		int index;
		for (int i = 1; i < pattern_length; ++i) {
			index = overlay[i - 1];
			// store previous fail position k to index;

			while (index >= 0 && pattern[i] != pattern[index + 1]) {
				index = overlay[index];
			}
			if (pattern[i] == pattern[index + 1]) {
				overlay[i] = index + 1;
			} else {
				overlay[i] = -1;
			}
		}

		return overlay;
	}

}
